/**
 * 我们可以使用 2*1 的小矩形横着或者竖着去覆盖更大的矩形,请问用n个2*1 的小矩形无重叠的覆盖一个 2*n 的大矩形
 * 总共有多少种方法
 * 比如:n=3 时,2*3 的矩形有3 中覆盖方法:
 */
/**
 * 动态规划:
 * 1.定义状态
 * 2.编写状态转移方程
 * 3.设置初始值
 * 用 n 个 2*1 的小矩形无重叠的覆盖一个2*n 的大矩形,每次放置的时候,无非两种方法:
 * 其中,横着放一个之后,下一个的方法已确定,虽然放置了两个矩形,但属于同一种放法
 *     竖着放一个之后,本轮放置已经完成,也属于一种方法
 * 所以当2*n 的大矩形被放慢的时候,就是用以上两种方式来放的
 * 用dp 法来解决:
 * 状态定义:f(n):用n个2*1的小矩形无重叠的覆盖一个2*n的大矩形所用的总方法数
 * 状态方程: f(n) = f(n-1)[最后一个竖着放]+f(n-2)[最后两个横着放]
 * 初始化:f(1)=1,f(2)=2,f(0)=1,注意,可以不考虑f(0)
 */
public class suanfa10 {
    public int rectCover(int target) {
        if (target <= 2) {
            return target;
        }
        int[] dp = new int[target+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= target ; i++) {
            dp[i] = dp[i-1] + dp[i-2];

        }
        return dp[target];
    }
}
